題目

有一群人正在排隊!每個人都用一個pair(h,k)描述，h是這個人的身高，k代表排在這個人前面有多少人的身高是高於或等於h的。
寫一個算法重排已每個人都能符合h,k的要求。

Heap(堆積)

• Heap是一個特殊的Complete Binary Tree
• 有分Max Heap與Min Heap
• Max Heap
  • 最大值位於root
  • 每一個節點的鍵值(key)不小於左右子節點的鍵值
• Min Heap
  • 最小值位於root
  • 每一個節點的鍵值(key)不大於左右子節點的鍵值
    
    https://hackmd.io/@smalleye/HJbAgo8YH

Priority Queue(優先佇列)

• 和一般Queue不同，Priority Queue中的每個元素都有各自優先權，優先權最高的元素能先被服務(存取)；相同按照其在優先佇列中的順序得到服務。
• 常使用Heap實作出Priority Queue

解法

在這裡 我們能使用C++ STL中提供的priority queue，定義出比較優先權的函式並符合題目要求，這樣我們只要將所有人插入到這個priority queue，在將所有人逐一拿出，這樣就能得到答案了!

依題目 2個相同高，我們就比較誰需要高的在前面人數比較多，不同高就比較身高。

Code

class cmp{
public:
    cmp(){}
    bool operator()(vector<int>& a, vector<int>& b){
        return (a[0] < b[0]) || (a[0] == b[0] && a[1] > b[1]);
    }
};

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        priority_queue< vector<int>, vector<vector<int>>, cmp> pq;
        vector<vector<int>> ans;
        
        for(int i = 0; i < people.size(); i++){
            pq.push(people[i]);
        }
        
        while(!pq.empty()){
            ans.insert(ans.begin()+pq.top()[1], pq.top());
            pq.pop();
        }
        return ans;
    }
};